package targetToOffer.twethDay;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author Godc
 * @description
 */
public class GetLeastNumbers {
    public static void main(String[] args) {
        GetLeastNumbersSolution s = new GetLeastNumbersSolution();
        int[] ints = {0,1,1,2,4,4,1,3,3,2};
//        s.sort(ints);
//        System.out.println(Arrays.toString(ints));
        int[] res = s.getLeastNumbers3(ints, 6);
        System.out.println(Arrays.toString(res));
    }
}
// TopK问题
class GetLeastNumbersSolution {
    /**
     * 方法一:利用大顶堆
     * @param arr
     * @param k
     * @return
     */
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 准备一个K大的数组
        int[] res = new int[k];
        int i = 0;
        while(i<k){
            res[i] = arr[i];
            i++;
        }
        sort(res);
        // 每次替换掉堆顶最大值，剩下的K堆就是前K小
        // 如果用小顶堆，所有的元素都要入队，建堆o(n)，每一次调整操作(logn)
        // 如果用 大顶堆，只需要入队K个，每一次调整操作(logK)
        while(i<arr.length){
            if(arr[i]<res[0]){
                res[0] = arr[i];
                adjustHeap(res,0,res.length);
            }
            i++;
        }
        return res;
    }

    /**
     * 方法二:部分快排o(n)
     * @param arr
     * @param k
     * @return
     */
    public int[] getLeastNumbers2(int[] arr, int k){
        if(k>=arr.length) return arr;
        quickSort(arr,0,arr.length-1,k);
        return Arrays.copyOf(arr,k);
    }
    public void quickSort(int[] arr,int left,int right,int k){
        int base = arr[left];
        int i = left,j = right;
        while(i<j){
            while(i<j&&arr[j]>=base) j--;
            while(i<j&&arr[i]<=base) i++;
            if(i<j){
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
        arr[left] = arr[i];
        arr[i] = base;
        if(i>k) quickSort(arr,left,i-1,k);
        if(i<k) quickSort(arr,i+1,right,k);
        return;
    }

    /**
     * 方法三:使用优先队列内部的堆
     * @return
     */
    public int[] getLeastNumbers3(int[] arr, int k){
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        if(k>=arr.length) return arr;
        // 默认小顶堆，需要重写比较器
        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
        for (int i : arr) {
            if(pq.size()<k){
                pq.offer(i);
            }else if(i<pq.peek()){
                pq.poll();
                pq.offer(i);
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = pq.poll();
        }
        return res;
    }



    public void adjustHeap(int[] arr,int i,int length){
        int temp = arr[i];
        // 从以i为根节点开始，开始调整
        for (int j = i*2+1; j < length; j = j*2+1) {
            if(j+1<length&&arr[j]<arr[j+1]){
                j++;//如果右节点更大，指向右节点
            }
            if(arr[j]>temp){
                arr[i] = arr[j];// 记录最大值
                i = j;
            }else{
                break;
            }
        }
        arr[i] = temp;// 将
    }
    public void sort(int[] arr){
        // 从下至上，从右致左开始调整，建堆复杂度为o(n)
        for (int i = arr.length/2-1; i >=0 ; i--) {
            adjustHeap(arr,i,arr.length);
        }
        // 本题不需要沉底操作
//        // 开始沉底操作,length个数，移动length-1次即可
//        for (int i = arr.length-1; i > 0 ; i--) {
//                int temp = arr[i];
//                arr[i] = arr[0];
//                arr[0] = temp;
//                // 调整范围逐渐减小
//                adjustHeap(arr,0,i);
//        }
    }
}